#include <algorithm>

using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x)
        : val(x), left(nullptr), right(nullptr)
    {
    }
};

class Solution {
public:
    int minDepth(TreeNode* root) 
    {
        if (root == nullptr)
        {
            return 0;
        }

        if (root->left && root->right)
        {
            return min(minDepth(root->left), minDepth(root->right)) + 1;    
        }

        return max(minDepth(root->left), minDepth(root->right)) + 1;
    }
};